package jzoffer;

import java.util.Arrays;

/**
 * Author:   dengxin
 * Date:     2020/6/16 10:40 上午
 * 重建二叉树
 * 根据某二叉树的前序遍历和中序遍历，重建该二叉树
 * 假设输入的前序遍历和中序遍历都不含重复数字
 * 前序遍历：{1, 2, 4, 7, 3, 5, 6, 8}
 * 中序遍历：{4, 7, 2, 1, 5, 3, 8, 6}
 *
 * 数组分段+递归
 */
public class jz4 {

    public static void main(String[] args) {
        int[] pre = {1, 2, 4, 7, 3, 5, 6, 8};
        int[] in = {4, 7, 2, 1, 5, 3, 8, 6};
        reConstructBinaryTree(pre, in);
    }

    /**
     * 根据前序数组和中序数组生成二叉树
     * @param pre 前序数组
     * @param in 中序数组
     * @return 重建二叉树的根节点
     */
    private static TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        //判断边界条件
        if (pre.length <= 0 || in.length <= 0) {
            return null;
        }
        int length = pre.length;
        //根据当前第一个节点确定根节点
        TreeNode root = new TreeNode(pre[0]);
        //在中序遍历中查找前序遍历第一个节点的位置i
        for (int i=0; i<length; i++) {
            if (in[i] == pre[0]) {
                //复制前序数组的[1,i)部分作为左节点的前序数组，中序数组的[0,i)部分作为左节点的中序数组
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1), Arrays.copyOfRange(in, 0,i));
                //复制前序数组的[i+1,n)部分作为右节点的前序数组，中序数组的[i+1,n)部分作为右节点的中序数组
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, length), Arrays.copyOfRange(in, i+1, length));
                break;
            }
        }
        return root;
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val) {
            this.val = val;
        }
    }

}
